\section{Unit 4：线性系统的迭代方法}

\begin{frame}{迭代方法概述}
    \begin{block}{迭代法 vs 直接法}
        \begin{itemize}
            \item \textbf{直接法}：有限步得到精确解（如高斯消元）
            \item \textbf{迭代法}：通过迭代逼近解，适用于大规模稀疏系统
            \item 优势：内存效率高，可并行，适用于病态问题
        \end{itemize}
    \end{block}
    
    \begin{block}{基本迭代格式}
        线性系统$A\mathbf{x} = \mathbf{b}$的迭代格式：
        \[ \mathbf{x}^{(k+1)} = B\mathbf{x}^{(k)} + \mathbf{c} \]
        \begin{itemize}
            \item $B$：迭代矩阵
            \item 收敛条件：$\rho(B) < 1$（谱半径）
            \item 收敛速度：由$\rho(B)$决定
        \end{itemize}
    \end{block}
    
    \begin{block}{迭代法分类}
        \begin{itemize}
            \item 定常迭代法：Jacobi, Gauss-Seidel, SOR
            \item Krylov子空间方法：CG, GMRES, BiCGSTAB
            \item 多重网格方法
            \item 预条件技术
        \end{itemize}
    \end{block}
\end{frame}

\begin{frame}{Jacobi方法}
    \begin{block}{Jacobi迭代格式}
        将$A$分解为$A = D - L - U$：
        \[ \mathbf{x}^{(k+1)} = D^{-1}(L + U)\mathbf{x}^{(k)} + D^{-1}\mathbf{b} \]
        \begin{itemize}
            \item $D$：$A$的对角部分
            \item $-L$：$A$的严格下三角部分
            \item $-U$：$A$的严格上三角部分
        \end{itemize}
    \end{block}
    
    \begin{block}{分量形式}
        对于$i = 1, 2, \ldots, n$：
        \[ x_i^{(k+1)} = \frac{1}{a_{ii}} \left( b_i - \sum_{j\neq i} a_{ij}x_j^{(k)} \right) \]
    \end{block}
    
    \begin{block}{收敛性分析}
        \begin{itemize}
            \item 收敛条件：$A$严格对角占优或不可约对角占优
            \item 迭代矩阵：$B_J = D^{-1}(L + U)$
            \item 可并行计算：各分量独立更新
        \end{itemize}
    \end{block}
\end{frame}

\begin{frame}{Gauss-Seidel方法}
    \begin{block}{Gauss-Seidel迭代格式}
        \[ \mathbf{x}^{(k+1)} = (D - L)^{-1}U\mathbf{x}^{(k)} + (D - L)^{-1}\mathbf{b} \]
    \end{block}
    
    \begin{block}{分量形式}
        对于$i = 1, 2, \ldots, n$：
        \[ x_i^{(k+1)} = \frac{1}{a_{ii}} \left( b_i - \sum_{j=1}^{i-1} a_{ij}x_j^{(k+1)} - \sum_{j=i+1}^n a_{ij}x_j^{(k)} \right) \]
        \begin{itemize}
            \item 使用最新计算值$x_j^{(k+1)}$
            \item 通常比Jacobi收敛更快
            \item 串行计算：分量依次更新
        \end{itemize}
    \end{block}
    
    \begin{block}{收敛性}
        \begin{itemize}
            \item 迭代矩阵：$B_{GS} = (D - L)^{-1}U$
            \item 收敛条件：$A$对称正定或严格对角占优
            \item $\rho(B_{GS}) \leq \rho(B_J)$（相同收敛条件）
        \end{itemize}
    \end{block}
\end{frame}

\begin{frame}{SOR与超松弛技巧}
    \begin{block}{逐次超松弛（SOR）方法}
        Gauss-Seidel的加权版本：
        \[ x_i^{(k+1)} = (1-\omega)x_i^{(k)} + \frac{\omega}{a_{ii}} \left( b_i - \sum_{j=1}^{i-1} a_{ij}x_j^{(k+1)} - \sum_{j=i+1}^n a_{ij}x_j^{(k)} \right) \]
        \begin{itemize}
            \item $\omega$：松弛因子（$0 < \omega < 2$）
            \item $\omega = 1$：Gauss-Seidel方法
            \item $\omega > 1$：超松弛（加速收敛）
            \item $\omega < 1$：低松弛（提高稳定性）
        \end{itemize}
    \end{block}
    
    \begin{block}{最优松弛因子}
        对于某些矩阵类（如Young性质A），存在最优$\omega_{opt}$：
        \[ \omega_{opt} = \frac{2}{1 + \sqrt{1 - \rho(B_J)^2}} \]
        \begin{itemize}
            \item 显著提高收敛速度
            \item 需要估计$\rho(B_J)$
            \item 实际中通过实验确定
        \end{itemize}
    \end{block}
\end{frame}

\begin{frame}{共轭梯度法（CG）}
    \begin{block}{CG方法特点}
        \begin{itemize}
            \item 适用于对称正定（SPD）矩阵
            \item Krylov子空间方法
            \item 有限步收敛（理论上$n$步）
            \item 超线性收敛（实际中远少于$n$步）
        \end{itemize}
    \end{block}
    
    \begin{block}{CG算法}
        \begin{enumerate}
            \item 初始化：$\mathbf{x}_0, \mathbf{r}_0 = \mathbf{b} - A\mathbf{x}_0, \mathbf{p}_0 = \mathbf{r}_0$
            \item 对于$k = 0, 1, \ldots$
            \begin{enumerate}
                \item $\alpha_k = \frac{\mathbf{r}_k^T\mathbf{r}_k}{\mathbf{p}_k^T A \mathbf{p}_k}$
                \item $\mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k \mathbf{p}_k$
                \item $\mathbf{r}_{k+1} = \mathbf{r}_k - \alpha_k A \mathbf{p}_k$
                \item $\beta_k = \frac{\mathbf{r}_{k+1}^T\mathbf{r}_{k+1}}{\mathbf{r}_k^T\mathbf{r}_k}$
                \item $\mathbf{p}_{k+1} = \mathbf{r}_{k+1} + \beta_k \mathbf{p}_k$
            \end{enumerate}
        \end{enumerate}
    \end{block}
    
    \begin{block}{收敛性}
        \[ \|\mathbf{x}_k - \mathbf{x}_*\|_A \leq 2\left(\frac{\sqrt{\kappa} - 1}{\sqrt{\kappa} + 1}\right)^k \|\mathbf{x}_0 - \mathbf{x}_*\|_A \]
        其中$\kappa = \kappa(A)$是条件数。
    \end{block}
\end{frame}

\begin{frame}{Krylov子空间方法}
    \begin{block}{Krylov子空间定义}
        \[ \mathcal{K}_m(A, \mathbf{r}_0) = \text{span}\{\mathbf{r}_0, A\mathbf{r}_0, A^2\mathbf{r}_0, \ldots, A^{m-1}\mathbf{r}_0\} \]
    \end{block}
    
    \begin{block}{主要Krylov方法}
        \begin{itemize}
            \item \textbf{CG}：对称正定矩阵
            \item \textbf{MINRES}：对称不定矩阵
            \item \textbf{GMRES}：非对称矩阵
            \item \textbf{BiCGSTAB}：非对称矩阵，避免转置
            \item \textbf{QMR}：拟最小残差法
        \end{itemize}
    \end{block}
    
    \begin{block}{GMRES算法}
        \begin{itemize}
            \item 适用于一般非对称矩阵
            \item 通过Arnoldi过程构造正交基
            \item 在Krylov子空间中最小化残差
            \item 需要重启避免存储增长
        \end{itemize}
    \end{block}
    
    \begin{block}{BiCGSTAB算法}
        \begin{itemize}
            \item 结合BiCG的稳定版本
            \item 避免转置矩阵运算
            \item 通常比GMRES更快收敛
            \item 可能不稳定
        \end{itemize}
    \end{block}
\end{frame}

\begin{frame}{稀疏矩阵求解器与预条件}
    \begin{block}{预条件技术思想}
        求解$M^{-1}A\mathbf{x} = M^{-1}\mathbf{b}$而不是$A\mathbf{x} = \mathbf{b}$
        \begin{itemize}
            \item $M$近似$A$但易于求逆
            \item 改善系数矩阵条件数
            \item 加速迭代收敛
        \end{itemize}
    \end{block}
    
    \begin{block}{常用预条件子}
        \begin{itemize}
            \item \textbf{Jacobi预条件子}：$M = \text{diag}(A)$
            \item \textbf{不完全LU分解}：$M = \tilde{L}\tilde{U} \approx A$
            \item \textbf{不完全Cholesky}：对称正定矩阵
            \item \textbf{多重网格预条件子}
            \item \textbf{域分解方法}
        \end{itemize}
    \end{block}
    
    \begin{block}{预条件CG算法}
        \begin{enumerate}
            \item 计算$\mathbf{r}_0 = \mathbf{b} - A\mathbf{x}_0$
            \item 解$M\mathbf{z}_0 = \mathbf{r}_0$
            \item $\mathbf{p}_0 = \mathbf{z}_0$
            \item 类似标准CG但使用预条件残差
        \end{enumerate}
    \end{block}
\end{frame}

\begin{frame}{迭代法应用领域}
    \begin{columns}
        \begin{column}{0.5\textwidth}
            \begin{block}{科学与工程计算}
                \begin{itemize}
                    \item 有限元分析
                    \item 计算流体动力学
                    \item 电磁场计算
                    \item 结构力学
                \end{itemize}
            \end{block}
            
            \begin{block}{偏微分方程}
                \begin{itemize}
                    \item 椭圆型方程（泊松方程）
                    \item 抛物型方程（热方程）
                    \item 双曲型方程（波动方程）
                    \item 特征值问题
                \end{itemize}
            \end{block}
        \end{column}
        \begin{column}{0.5\textwidth}
            \begin{block}{数据科学与机器学习}
                \begin{itemize}
                    \item 最小二乘问题
                    \item 正则化回归
                    \item 图Laplacian系统
                    \item 核方法
                \end{itemize}
            \end{block}
            
            \begin{block}{优化问题}
                \begin{itemize}
                    \item 牛顿法中的线性系统
                    \item 内点法
                    \item 二次规划
                    \item 半定规划
                \end{itemize}
            \end{block}
        \end{column}
    \end{columns}
\end{frame}

\begin{frame}{本章重点总结}
    \begin{block}{核心迭代方法}
        \begin{itemize}
            \item 定常迭代法：Jacobi, Gauss-Seidel, SOR
            \item Krylov子空间方法：CG, GMRES, BiCGSTAB
            \item 预条件技术
            \item 收敛性分析
        \end{itemize}
    \end{block}
    
    \begin{block}{数值特性}
        \begin{itemize}
            \item 收敛条件：谱半径$\rho(B) < 1$
            \item 收敛速度：由条件数决定
            \item 稳定性：重启策略，重新正交化
            \item 并行性：Jacobi可并行，Gauss-Seidel串行
        \end{itemize}
    \end{block}
    
    \begin{block}{学习目标}
        \begin{itemize}
            \item 掌握各种迭代法的原理和实现
            \item 能够分析算法的收敛性
            \item 理解预条件技术的作用
            \item 能够选择适当的迭代方法
        \end{itemize}
    \end{block}
\end{frame}